﻿/* This is initial version of a Stack class
 * based on Eric Lippert blog post
 */

namespace EVB.Collections.Immutable
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Diagnostics.CodeAnalysis;
    using System.Runtime.InteropServices;
    using System.Threading;

    /// <summary>
    /// Represents an immutable last-in-first-out (LIFO) collection of instances of the same arbitrary type.
    /// </summary>
    /// <typeparam name="T">Specifies the type of elements in the stack.</typeparam>
    [ComVisible(false)]
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(StackDebugView<>))]
    [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
    [SuppressMessage("Microsoft.Naming", "CA1711:IdentifiersShouldNotHaveIncorrectSuffix")]
    public sealed class Stack<T> : IEnumerable<T>, ICollection, IEnumerable
    {
        /// <summary>
        /// Empty immutable stack is a starting point for an immutable stack population.
        /// </summary>
        [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
        [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
        public static readonly Stack<T> Empty = new Stack<T>();

        private readonly T _head;
        private readonly Stack<T> _tail;
        private readonly int _count;

        [NonSerialized]
        private object _syncRoot;

        private Stack() { }

        private Stack(T head, Stack<T> tail)
        {
            _head = head;
            _tail = tail;
            _count = tail.Count + 1;
        }

        /// <summary>
        /// Determines whether this <see cref="Stack{T}"/> collection is empty.
        /// </summary>
        public bool IsEmpty { get { return _count == 0; } }

        /// <summary>
        /// Returns the object at the top of the <see cref="Stack{T}"/> without removing it.
        /// </summary>
        /// <exception cref="InvalidOperationException"> if used on empty stack.</exception>
        public T Peek
        {
            get
            {
                if (IsEmpty)
                    throw new InvalidOperationException(Properties.Resources.StackEmpty);

                return _head;
            }
        }

        /// <summary>
        /// Removes the object at the top of the <see cref="Stack{T}"/> and returns the <see cref="Stack{T}"/>.
        /// </summary>
        /// <returns>The <see cref="Stack{T}"/> without removed item.</returns>
        /// <exception cref="InvalidOperationException"> if used on empty stack.</exception>
        public Stack<T> Pop()
        {
            if (IsEmpty)
                throw new InvalidOperationException(Properties.Resources.StackEmpty);

            return _tail;
        }

        /// <summary>
        /// Inserts an object at the top of the <see cref="Stack{T}"/> and returns a new <see cref="Stack{T}"/>.
        /// </summary>
        /// <param name="value">The item to push onto the stack.</param>
        /// <returns>A new <see cref="Stack{T}"/> with inserted object.</returns>
        public Stack<T> Push(T value) { return new Stack<T>(value, this); }

        /// <summary>
        /// Copies the <see cref="Stack{T}"/> to a new array.
        /// </summary>
        /// <returns>A new array containing copies of the elements of the <see cref="IStack{T}"/>.</returns>
        public T[] ToArray()
        {
            var result = new T[_count];
            int index = result.Length - 1;

            for (var stack = this; !stack.IsEmpty; stack = stack.Pop())
                result[index--] = stack.Peek;

            return result;
        }

        /// <summary>
        /// Returns the number of elements in a <see cref="Stack{T}"/>.
        /// </summary>
        public int Count { get { return _count; } }

        #region IEnumerable members

        /// <summary>
        /// Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection.</returns>
        public IEnumerator<T> GetEnumerator()
        {
            for (var stack = this; !stack.IsEmpty; stack = stack.Pop())
                yield return stack.Peek;
        }

        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>An <seealso cref="IEnumerator"/> object that can be used to iterate through the collection.</returns>
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

        #endregion

        #region ICollection members

        /// <summary>
        /// Copies the <see cref="Stack{T}"/> to an existing one-dimensional array, starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array that is the destination of the elements copied from <see cref="Stack{T}"/>.</param>
        /// <param name="index">The zero-based index in <paramref name="array"/> at which copying begins.</param>
        /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than zero.</exception>
        /// <exception cref="ArgumentException">The number of elements in the source <see cref="Stack{T}"/> is greater than the available space from <paramref name="index"/> to the end of the destination <paramref name="array"/>.</exception>
        public void CopyTo(T[] array, int index)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            ToArray().CopyTo(array, index);
        }

        void ICollection.CopyTo(Array array, int index)
        {
            if (array == null)
                throw new ArgumentNullException("array");

            ToArray().CopyTo(array, index);
        }

        bool ICollection.IsSynchronized
        {
            get { return true; }
        }

        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                    Interlocked.CompareExchange(ref _syncRoot, new object(), null);

                return _syncRoot;
            }
        }

        #endregion
    }
}